import { scan } from './LexerParser';

const Syntax = {
  Program: [
    ['StatementList', 'EOF'],
  ],
  StatementList: [
    ['Statement'],
    ['StatementList', 'Statement'],
  ],
  Statement: [
    ['IfStatement'],
    ['WhileStatement'],
    ['ExpressionStatement'],

    ['VariableDeclaration'],
    ['FunctionDeclaration'],

    ['Block'],
    ['BreakStatement'],
    ['ContinueStatement'],
  ],
  Block: [
    ['{', 'StatementList', '}'],
    ['{', '}'],
  ],
  BreakStatement: [
    ['break', ';'],
  ],
  ContinueStatement: [
    ['continue', ';'],
  ],
  ExpressionStatement: [
    ['Expression', ';'],
  ],
  WhileStatement: [
    ['while', '(', 'Expression', ')', 'Statement'],
  ],
  IfStatement: [
    ['if', '(', 'Expression', ')', 'Statement'],
  ],
  VariableDeclaration: [
    ['var', 'IdentifierName', ';'],
  ],
  FunctionDeclaration: [
    ['function', 'IdentifierName', '(', ')', '{', 'StatementList', '}'],
  ],
  Expression: [
    ['AssignmentExpression'],
  ],
  AssignmentExpression: [
    ['LogicalORExpression'],
    ['LeftHandSideExpression', '=', 'LogicalORExpression'],
  ],
  LogicalORExpression: [
    ['LogicalANDExpression'],
    ['LogicalORExpression', '||', 'LogicalANDExpression'],
  ],
  LogicalANDExpression: [
    ['AdditiveExpression'],
    ['LogicalANDExpression', '&&', 'AdditiveExpression'],
  ],
  AdditiveExpression: [
    ['MultiplicativeExpression'],
    ['AdditiveExpression', '+', 'MultiplicativeExpression'],
    ['AdditiveExpression', '-', 'MultiplicativeExpression'],
  ],
  MultiplicativeExpression: [
    ['LeftHandSideExpression'],
    ['MultiplicativeExpression', '*', 'LeftHandSideExpression'],
    ['MultiplicativeExpression', '/', 'LeftHandSideExpression'],
  ],
  LeftHandSideExpression: [
    ['CallExpression'],
    ['NewExpression'],
  ],
  CallExpression: [
    ['MemberExpression', 'Arguments'],
    ['CallExpression', 'Arguments'],
  ],
  Arguments: [
    ['(', ')'],
    ['(', 'ArgumentList', ')'],
  ],
  ArgumentList: [
    ['AssignmentExpression'],
    ['ArgumentList', ',', 'AssignmentExpression'],
  ],
  NewExpression: [
    ['MemberExpression'],
    ['new', 'NewExpression'],
  ],
  MemberExpression: [
    ['PrimaryExpression'],
    ['PrimaryExpression', '.', 'IdentifierName'],
    ['PrimaryExpression', '[', 'Expression', ']'],
  ],
  PrimaryExpression: [
    ['(', 'Expression', ')'],
    ['Literal'],
    ['IdentifierName'],
  ],
  Literal: [
    // 基本数据类型
    ['NumericLiteral'],
    ['StringLiteral'],
    ['BooleanLiteral'],
    ['NullLiteral'],
  
    // 复杂数据类型
    ['ObjectLiteral'],
    ['ArrayLiteral'],
    ['RegularExpression'],
  ],
  ObjectLiteral: [
    ['{', '}'],
    ['{', 'PropertyList', '}'],
  ],
  PropertyList: [
    ['Property'],
    ['PropertyList', ',', 'Property'],
  ],
  Property: [
    ['IdentifierName', ':', 'Expression'],
    ['StringLiteral', ':', 'Expression'],
  ],
};

export type Rule = keyof typeof Syntax;

export function isRule(rule: string): rule is Rule {
  return Syntax.hasOwnProperty(rule);
}

const hash: Record<string, Record<string, any>> = {};

// 计算闭包
export function closure(state: { [key: string]: any }) {
  hash[JSON.stringify(state)] = state;

  const queue: string[] = [];

  for (let symbol in state) {
    if (symbol.match(/^\$/)) {
      continue;
    }

    queue.push(symbol);
  }

  while (queue.length > 0) {
    const symbol = queue.shift()!;

    if (!isRule(symbol)) {
      continue;
    }

    for (let rule of Syntax[symbol]) {
      if (state[rule[0]] == null) {
        queue.push(rule[0]);
      }

      let current = state;

      for (let part of rule) {
        if (current[part] == null) {
          current[part] = {};
        }

        current = current[part];
      }

      current.$reduceType = symbol;
      current.$reduceLength = rule.length;
    }
  }

  for (let symbol in state) {
    if (symbol.match(/^\$/)) {
      continue;
    }

    if (hash[JSON.stringify(state[symbol])]) {
      state[symbol] = hash[JSON.stringify(state[symbol])];
    } else {
      closure(state[symbol]);
    }
  }
}

const end = {
  $isEnd: true,
};

const start = {
  'Program': end,
};

closure(start);

// 移进
function shift(
  symbol: Record<string, any>,
  stack: Record<string, any>[],
  symbolStack: Record<string, any>[],
) {
  let state = stack[stack.length - 1];

  if (symbol.type in state) {
    stack.push(state[symbol.type]);
    symbolStack.push(symbol);
  } else {
    shift(reduce(stack, symbolStack), stack, symbolStack);
    shift(symbol, stack, symbolStack);
  }
}

// 规约
function reduce(stack: Record<string, any>[], symbolStack: Record<string, any>[]) {
  const state = stack[stack.length - 1];

  if (state.$reduceType) {
    let children = [];

    for (let i = 0; i < state.$reduceLength; i++) {
      stack.pop();
      children.push(symbolStack.pop());
    }

    return {
      type: state.$reduceType,
      children: children.reverse(),
    };
  } else {
    throw new Error('Unexpected token');
  }
}

// LR 自下而上的语法分析方法
export function parse(source: string) {
  const stack: Record<string, any>[] = [start];
  const symbolStack: Record<string, any>[] = [];

  for (let symbol of scan(source)) {
    shift(symbol, stack, symbolStack);
  }

  return reduce(stack, symbolStack);
}
